package net.flintx.array;

import java.util.ArrayList;
import java.util.List;

public class PascalTriangle2 {
    public List<Integer> getRow(int rowIndex) {
        /**
         * getRow
         *
         * @Description:
         *  Given an index k, return the k-th row of the Pascal's triangle.
         *  Note:
         *      Could you optimize your algorithm to use only O(k) extra space?
         * @Example:
         *  Input:  k = 3
         *  Output:
         *      [1,3,3,1]
         * @Params: [rowIndex]
         * @Return: List<Integer>
         * @Date: 2018/1/7
         */

        List<Integer> row = new ArrayList<>();
        row.add(1);
        if (rowIndex == 0) {
            return row;
        }
        row.add(1);
        if (rowIndex == 1) {
            return row;
        }
        List<Integer> temp = new ArrayList<>();
        for (int i = 2; i <= rowIndex; i++) {
            temp.add(1);
            for (int j = 1; j < i; j++) {
                temp.add(row.get(j - 1) + row.get(j));
            }
            temp.add(1);
            row.clear();
            row.addAll(temp);
            temp.clear();
        }
        return row;
    }

    public List<Integer> betterMethod(int rowIndex) {
        List<Integer> res = new ArrayList<>();
        if (rowIndex < 0) {
            return res;
        }
        for (int i = 0; i <= rowIndex; i++) {
            res.add(0, 1);
            for (int j = 1; j < res.size() - 1; j++) {
                res.set(j, res.get(j) + res.get(j + 1));
            }
        }
        return res;
    }
}
